The present invention relates generally to a technique for ensuring security in a computer network. More particularly, the present invention is concerned with a method of realizing an elliptic curve cryptography (encryption/decryption), an apparatus for carrying out the method and a recording medium for storing the same in the form of a program executable with a computer.
The elliptic curve cryptography (encryption/decryption) is one of the public key cryptology algorithms invented by V. Miller and N. Koblitz independently. As the postulation for the public-key cryptograph technology imposed from the viewpoint of security, discovery of a private key on the basis of the counterpart public key laid open to the general public must be made impossible in practice. On the other hand, the public key cryptosystem requires intrinsically a lot of time for encryption and decryption when compared with the private key cryptosystem. Thus, in the present state of the art, there exists a great demand for a high-speed processing technique for enabling encryption and decryption in the public key cryptosystem. Under the circumstances, as the public key cryptograph technique which can satisfy both requirements for the security and the high-speed processing susceptibility which are, so to say, contradictory to each other, the elliptic curve cryptography which has more competence for dealing with the above problem than the RSA (Rivest, Shamir & Adleman) cryptography and the ElGamal cryptography both known heretofore is now attracting attention.
The elliptic curve cryptograph can be represented by the standard form of an elliptic curve in a finite prime field, i.e., y2=x3+ax+b (4a3+27b2≠0) or alternatively by the standard form of an elliptic curve in a finite field of characteristic 2 (which may also be referred to as the extension field of “2”), i.e., y2+xy=x3+ax2+b (b≠0). By adding a point at infinity to the points on such curve, an Abelian group is made available. In this conjunction, the Abelian group arithmetic will be represented by plus sign (+). Further, in conjunction with the arithmetics for X and Y which differ from each other, “X+Y” will be referred to as the addition arithmetic. Furthermore, “X+X” will be referred to as the doubling arithmetic and represented by “2X”.
In order to facilitate computations involved in the elliptic curve cryptography, a point (X, Y) on an elliptic curve in the affine coordinate system may also be expressed in terms of the projective coordinates. At this juncture, let's suppose the projective coordinate system in which [X, Y, Z]=[λ2X, λ3Y, λZ] applies valid for a given λ≠0. Then, there can be established such correspondences between the affine coordinates and the projective coordinates as mentioned below. Namely, the affine coordinates (x, y) can be represented by the projective coordinates [x, y, 1] while the projective coordinates [X, Y, Z] can be represented by the affine coordinates (X/(Z)2, Y/(Z)3). Further, in the projective coordinate system, it applies valid that −[X, Y, Z]=[X, −Y, Z].
In the elliptic curve cryptography, an elliptic curve in a finite field is made use of for making usable a set of points which constitutes a finite field of the elliptic curve. In this conjunction, the order of the elliptic curve is represented by a number of points of the elliptic curve. In the following, the result of addition of “P” s times, i.e., P+P+ . . . +P where the number of “P” is s, will be referred to as the s-multiplied point of “P”. When the arithmetic for determining the s-multiplied point of P is represented by “sP”, the order of the point “P” on the elliptic curve is given by n=112 which satisfies the conditions that nP=0, 1≦m<n and mP≠0.
The key for the elliptic curve cryptography is composed of an elliptic curve, a base point, a public key and a private key. In more concrete, the key of the elliptic curve cryptograph is composed of coefficients a and b of the elliptic curve, the point P (base point) whose order is a prime number, a finite field element d (private key) and a point Q (public key) given by a product of the base point multiplied by the private key (i.e., Q=dp). Incidentally, it is to be added that the elliptic curve, the base point and the public key are the laid-open information. Further, the public key and the private key assume respective values which differ from one to another user, while the elliptic curve and the base point assume respective values which are common to the users.
In the elliptic curve cryptography, a scalar multiplication (SB) arithmetic for a given point R is adopted for the data encryption, generation of a digital signature and the verification of the digital signature. The scalar multiplication can be realized through combination of the addition arithmetic and the doubling arithmetic mentioned previously. However, computation for each of such addition arithmetic and doubling arithmetic necessarily requires execution of division arithmetic once. In general, division of the finite field takes lots of time. For this reason, efforts have heretofore been paid for establishing such a computation method which can avoid the division arithmetic.
As an approach for evading the division of the finite field, addition arithmetic and doubling arithmetic in the projective space as well as expressions or formulae for realization thereof have already been proposed. For more particulars, reference should be made to D. V. Chudnovsky and G. V. Chudnovsky: “SEQUENCES OF NUMBERS GENERATED BY ADDITION IN FORMAL GROUPS AND NEW PRIMALITY AND FACTORIZATION TESTS”, Advances in Applied Mathematics, 7. 385-434, 1986. In this conjunction, it is noted that the computation time taken for the prime field multiplication is ordinarily by far longer than that taken for the prime field addition/subtraction. Thus, the overall computation time or overhead can be evaluated on the basis of the number of arithmetic processes involved in the prime field multiplication. In that case, the addition arithmetic requires execution of the prime field multiplication (inclusive of squaring arithmetic) sixteen times. In the doubling arithmetic, the prime field multiplication has to be performed ten times. For more particulars, reference is to be made to the literature cited above. Further, it is reported that for the coefficient a of the elliptic curve, residual multiplication arithmetic has to be performed eight times in the case where a=−3.
Further, according to the teachings disclosed in P. Montgomery: “SPEEDING THE POLLARD AND ELLIPTIC CURVE METHODS OF FACTORIZATION”, Mathematics of Computation Vol. 48, No. 177, pp. 243-264 (1987), it is reported that when the standard form of an elliptic curve in a finite prime field, i.e., By2=x3+Ax2+Bx, is employed for addition of points P0(x0, y0) and P1(x1, y1) as given by P3(x3, y3) and subtraction thereof as given by P4(x4, y4), i.e., when P1+P0=P3 and P1−P0=P4, then x3 can be determined speedily from X0, x1, x4. In more concrete, it is reported that x3 can be determined by executing six times the prime field multiplication. Further, in the case where the double point of P1 is given by P5(x5, y5), x5 can be determined only from x1 by performing multiplication five times. By taking advantage of this feature, x-coordinate of scalar multiple (scalar value d) of the point R can be determined from Rx in the manner described below.
Presuming that the initial value is [R, 2R] and that mR represents the x-coordinate of the point R multiplied by m, the scalar value d is exploded or developed to a bit string in the binary notation. Then, starting from the most significant bit of d, it is validated that [mR, (m+1)R]→[2mR, 2(m+1)R] for the bit “0” of d, and [mR, (m+1)R]→[(2m+1)R, 2(m+1)R] for the bit “1” of d, where (m+1)R−mR=R and (m+1)R+mR=(2m+1)R.
In this manner, the scalar multiplication sP can be realized by performing the prime field multiplication (inclusive of squaring) ten times (6+5) for each bit. Hereinafter, the procedure or algorithm described above will be referred to as the Montgomery method.
On the other hand, the standard form of an elliptic curve on the finite field of characteristic 2 (extension field of “2”) is given by y2+xy=x3+ax2+b (b≠0). For such elliptic curve, the scalar multiplication arithmetic can be realized through combination of the addition arithmetic and the doubling arithmetic. Rules for the addition arithmetic and the doubling arithmetic are set forth in IEEE: P1363/D2 “STANDARD SPECIFICATION FOR PUBLIC KEY CRYPTOGRAPHY” (1998). By resorting to the arithmetic in the finite field of characteristic 2 (extension field of “2”), squaring and addition/subtraction can be realized very speedily when compared with mutually different multiplications. Thus, the computation overhead involved in the arithmetics in the finite field of characteristic 2 can be evaluated by the number of times the mutually different multiplications are to be performed. The addition arithmetic requires execution of multiplication fifteen times while the doubling arithmetic requires execution of multiplication five times. However, it should be noted that in the elliptic curve cryptography based on the finite field of characteristic 2, no arithmetic algorithm is known in which the Montgomery method is resorted to.
For the elliptic curve which can ensure security, it is necessary to set parameters a and b which allow the order #E(Fq) of the elliptic curve to have a large prime factor r. In the case where the order #E(Fq) of the elliptic curve is given by kr, the prime factor r can assume a large prime number by selecting a small integer for k. As to the method of setting the parameters of the elliptic curve having a large prime factor r as the order, reference may be made to Henri Cohen: “A COURSE IN COMPUTATIONAL ALGEBRAIC NUMBER THEORY”, GTM138, Springer (1993) p. 464, Atkin's Test.
Next, problems of cipher text attack and defense against the attack will be considered. In recent years, trials for attacking the cipher text as well as the measures for defending the cipher text against the attacks have been studied. More specifically, as to the attack on the cipher text, there can be mentioned in addition to the classical or theoretical cryptanalysis a differential power analysis (DPA in short) which tries to decode or decrypt the cipher text by processing statistically waveform representing current consumption, a timing attack trying to decode by analyzing statistically differences in the cipher processing time and others which rely on the analyses of leak information. Of course, the measures for defending the cipher against such attacks have also been developed. However, most of the defense measures have been realized primarily by physically incorporating the defense function in hardware circuit itself destined, for example, for IC cards.
The conventional elliptic curve cryptographies described above suffer problems mentioned below. As is apparent from the foregoing, in the elliptic curve cryptography in the finite field of characteristic 2, there is known no arithmetic in which the Montgomery method is adopted. Further, in the studies concerning the elliptic curve cryptographies, importance has been put primarily on the development of high-speed execution methods and generation of such elliptic curve which can ensure security as viewed from the standpoint of cryptanalysis. By contrast, no efforts have been paid to the development of defense technologies for defending the ciphers against the attack of the leak information analysis type. In the data decryption processing of the elliptic curve cryptology, arithmetic operation for multiplying a point (x, y) on a given elliptic curve by the private key d, i.e., D(x, y), is performed. In that case, deviation information of the private key d may possibly leak, being reflected in the consumed current waveform and the cipher processing time, which will give a clue to the differential power analysis (DPA) attack and the timing attack.